/**
 * dfs
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} source
 * @param {number} destination
 * @return {boolean}
 */
var validPath = function (n, edges, source, destination) {
    let graph = new Array(n).fill(0).map(() => new Array()),
        visited = new Array(n).fill(false);

    for (let [x, y] of edges) {
        graph[x].push(y)
        graph[y].push(x)
    }

    return dfs(source, destination, visited, graph)
};

function dfs(source, destination, visited, graph) {
    visited[source] = true
    if (source === destination) {
        return true
    }

    for (let nextStep of graph[source]) {
        if (visited[nextStep] === false) {
            if (dfs(nextStep, destination, visited, graph)) return true
        }
    }
    return false
}



/**
 * bfs
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} source
 * @param {number} destination
 * @return {boolean}
 */
var validPath = function (n, edges, source, destination) {
    let graph = new Array(n).fill(0).map(() => new Array()),
        visited = new Array(n).fill(false);

    for (let [x, y] of edges) {
        graph[x].push(y)
        graph[y].push(x)
    }

    let queue = [source];
    visited[source] = true;
    while (queue.length > 0) {
        let node = queue.shift()
        if (node === destination) {
            return true
        }
        for (let nextStep of graph[node]) {
            if (visited[nextStep] === false) {
                visited[nextStep] = true
                queue.push(nextStep)
            }
        }
    }
    return false
};


/**
 * 并查集：判断两个元素在不在一个集合中。
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} source
 * @param {number} destination
 * @return {boolean}
 */
var validPath = function (n, edges, source, destination) {
    let index = 0,
        // 初始化并查集
        father = new Array(n).fill(0).map(() => index++);

    // 判断a和b是否是同一个根,是否在同一个集合,是否可以互通
    function isSame(a, b) {
        a = find(a)
        b = find(b)
        return a === b
    }

    // 在并查集中寻a的根,同时做路径压缩
    function find(a) {
        return a === father[a] ? a : father[a] = find(father[a])
    }

    // 将b>a这条边加入并查集，其实将a>b这条边加入并查集也可以
    function join(a, b) {
        a = find(a)
        b = find(b)
        if (a === b) return
        father[b] = a
    }

    for (let [x, y] of edges) {
        join(x, y)
    }

    return isSame(source, destination)
}
